﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading;

namespace HeapSort
{
	class Program
	{
		/// <summary>
		/// 堆排序时间复杂度：O(NlogN)
		/// </summary>
		/// <param name="args"></param>
		static void Main(string[] args)
		{
			//2次比较
			for (int i = 1; i <= 5; i++)
			{
				List<int> list=new List<int>();
				//随机选择1000个数到数组中
				for (int j = 0; j < 500; j++)
				{
				    Thread.Sleep(j);
				    list.Add(new Random((int) DateTime.Now.Ticks).Next(0,100000));
				}
				Console.WriteLine("\n第"+i+"次比较：");
				Stopwatch watch=new Stopwatch();
				watch.Start();
				var result = list.OrderBy(single => single).ToList();
				watch.Stop();
				Console.WriteLine("\n快速排序耗费时间："+watch.ElapsedMilliseconds);
				Console.WriteLine("输出前十个数是："+string.Join(",",result.Take(10).ToList()));
				watch.Start();
				//堆排序
				//new HeapSortClass().HeapSort(list);
				//前k大堆排序
				result = new HeapSortClass().HeapSort(list,10);
				watch.Stop();
				//堆排序
				//Console.WriteLine("\n堆排序耗费时间：" + watch.ElapsedMilliseconds);
				//Console.WriteLine("输出前十个数是：" + string.Join(",", list.Take(10).ToList()));
				//前k大堆排序
				Console.WriteLine("\n前k大堆排序耗费时间：" + watch.ElapsedMilliseconds);
				Console.WriteLine("输出前十个数是：" + string.Join(",", result.Take(10).ToList()));
			}
			Console.ReadLine();
		}
	}

	public class HeapSortClass
	{
		public void HeapAdjust(List<int> list,int parent,int length)
		{
			//temp来保存当前的父节点
			int temp = list[parent];
			//得到父节点的左孩子 (二叉树定义)
			int child = 2*parent + 1;
			while (child<length)
			{
				//如果parent有右孩子，则要判断左孩子是否小于右孩子
				if (child + 1 < length && list[child] < list[child + 1])
					child++;
				//父亲节点大于子节点，就不用交换
				if(temp >=list[child])
					break;
				//将较大子节点的值赋给父亲节点
				list[parent] = list[child];
				//然后将子节点做为父节点，已防止是否破坏根堆时重新构造
				parent = child;
				//找到该父节点较小的左孩子节点
				child = 2*parent + 1;
			}
			//最后将temp值赋值给较大的子节点,以形成两值交换
			list[parent] = temp;
		}

		/// <summary>
		/// 堆排序
		/// </summary>
		/// <param name="list"></param>
		public void HeapSort(List<int> list)
		{
			//list.count/2-1 就是堆中父节点的个数
			for (int i = list.Count/2-1; i >=0; i--)
			{
				HeapAdjust(list,i,list.Count);
			}
			//最后输出堆元素
			for (int i = list.Count-1; i >0; i--)
			{
				//堆顶与当前堆的第i个元素进行值对调
				int temp = list[0];
				list[0] = list[i];
				list[i] = temp;
				//因为两值交换，可能破坏根堆，所以必须重新构造
				HeapAdjust(list,0,i);
			}
		}

		/// <summary>
		/// 堆排序
		/// </summary>
		/// <param name="list">待排序的集合</param>
		/// <param name="top">前k大</param>
		public List<int> HeapSort(List<int> list,int top)
		{
			List<int> topNode=new List<int>();
 			//list.count/2-1 就是堆中父节点的个数
			for (int i = list.Count / 2 - 1; i >= 0; i--)
			{
				HeapAdjust(list, i, list.Count);
			}
			//最后输出堆元素
			for (int i = list.Count - 1; i >= list.Count-top; i--)
			{
				//堆顶与当前堆的第i个元素进行值对调
				int temp = list[0];
				list[0] = list[i];
				list[i] = temp;

				//将最大值加入集合
				topNode.Add(temp);
				//因为两值交换，可能破坏根堆，所以必须重新构造
				HeapAdjust(list, 0, i);
			}
			return topNode;
		}
	}
}
